#include <vector>
#include <list>
#include <iostream>

using namespace std;

// vector<int> v {1, 2, 3, 4, 5}
// vector 来说，它的元素在内存中是连续存储，一个挨着一个存储的
// 元素之间是没有缝隙的。

// vector / deque 在容器的中间位置插入元素的时候，效率都不好。
// list 就是为了解决这个问题：如何更高效的在容器的中间位置插入和删除元素。

// 1 -> 2 -> 3 -> 4 -> 5
// Node 节点
class Node {
public:
  // 构造函数
  Node(int v, Node *n = nullptr) : value(v), next(n) {}

public:
  int value;
  Node *next;
};

// 链表
class List {
public:
  // 构造函数
  List(Node *pNode = nullptr) : head(pNode) {}

  // 在链表中查找是否存在值为 n 的节点，存在 true 否则 false
  bool find(int n) {
    Node *p = head;

    while (p != nullptr) {
      if (p->value == n) {
        return true;
      }

      p = p->next;
    }
    
    return false;
  }

private:
  Node *head;
};

int main(int argc, char const *argv[])
{
  /* code */
  Node n1 {1};
  Node n2 {2};
  Node n3 {3};
  Node n4 {4};
  Node n5 {5};

  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n4;
  n4.next = &n5;

  Node *head = &n1;

  while (head != nullptr) {
    cout << head->value << endl;
    head = head->next;
  }

  List l{&n1}; // 空链表

  cout << l.find(3) << endl; // true
  cout << l.find(10) << endl; // false

  list<int> ll;
  return 0;
}
